package src.week8.实验;

import src.week8.实验.LinkedBinaryTree;

public class reconstruct {
    public static class TreeNode {
        public String data;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(String data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "TreeNode [data=" + data + ", left=" + left + ", right=" + right
                    + "]";
        }
    }

    public static TreeNode rebuildBinaryTree(String preorder[], String inorder[]) {
        if (preorder == null || inorder == null) {
            return null;
        }
        TreeNode root = rebuildBinaryTreeCore(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
        return root;
    }
    public static TreeNode rebuildBinaryTreeCore(String preorder[], int startPreorder,
                                                 int endPreorder, String inorder[], int startInorder, int endInorder) {
        if (startPreorder > endPreorder || startInorder > endInorder) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[startPreorder]);
        for (int i = startInorder; i <= endInorder; i++) {
            if (preorder[startPreorder] == inorder[i]) {
                root.left = rebuildBinaryTreeCore(preorder, startPreorder + 1, startPreorder + (i - startInorder), inorder, startInorder, i - 1);
                root.right = rebuildBinaryTreeCore(preorder, (i - startInorder) + startPreorder + 1, endPreorder, inorder, i + 1, endInorder);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        String preorder[] = {"A", "B", "D", "H", "I", "E", "J", "M", "N", "C", "F", "G", "K", "L"};
        String inorder[] = {"H", "D", "I", "B", "E", "M", "J", "N", "A", "F", "C", "K", "G", "L"};
        TreeNode treeNode = rebuildBinaryTree(preorder, inorder);
        System.out.println(treeNode);
    }
}







